# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/8/3 8:52
"""


"""
模式匹配：KMP（Knuth Morris Pratt）算法
定义next[j]函数，表征模式P种最大相同首子串和尾子串(真子串)的长度

表明当模式中第j个字符与主串中相应字符‘失配’时，在模式中需重新和主串中该字符
及逆行比较的字符的位置
k=next[j]
j=1,不比较，next[j]==0
p1...pk-1=P(j-(k-1))...pj-1, next[j]=max{k}
其他情况，next[j]=1

分析结论：主串中的i可以不回溯，模式向右华东到的新比较起点k，并且k仅与模式串P(模式串)有关！

如何由当前部分匹配结果确定模式向右华东的新比较起点k?
    计算next[j]的方法：
    - j==1，next[j]==0,表示根本不进行字符比较
    - j>1，next[j]的值为：
        模式串的位置从1到j-1构成的串所出现的首位相同的子串的最大长度+1
    - 当无首尾相同的子串next[j]的值为1
        next[j]=1表示从模式串头部进行字符比较


KMP思想：
    设有主串s和子串t，子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串，
    把子串t称为模式串，因此定位也成为模式匹配。

算法流程：
    step1:在串S和串T中分别设比较的起始下标i和j;
    step2：循环直到S中所剩字符长度小于T的长度或T中所有字符均比较完毕
        if S[i]==T[j],继续比较S和T的下一个字符；否则
        将j向右滑动到next[j]的位置，即j=next[j]
        if j==0,则i和j分别加1,准备下一趟比较
    step3:如果T中所有字符均比较完毕，则返回匹配的起始下标；否则返回0

"""


def get_next_j(s, j):
    if j == 1:
        return 0
    else:
        tmp_s = s[:j - 1]
        k = 0
        i = 1
        while i < j - 1:
            # print(f"tmp_s={tmp_s},tmp_s[:k]={tmp_s[:i]},tmp_s[j - k:]={tmp_s[j-i-1:]}")
            if tmp_s[:i] == tmp_s[j - i - 1:]:
                k = len(tmp_s[:i]) if len(tmp_s[:i]) > k else k
            i += 1
        return k + 1



def string_KMP(lead_str, T_str):
    """
    基于KMP算法实现模式匹配
    Args:
        lead_str: 主串
        T_str: 模式串

    Returns:
        True if success else False

    """
    #计算next_j
    next_j=[get_next_j(T_str,i+1) for i in range(len(T_str))]
    print(f'next_j={next_j}')

    """
    新增一个nextval列表
    """
    nextval=[0]*len(T_str)
    i, j = 0, 1
    while len(lead_str[i:]) > len(T_str[j:]) and j-1 < len(T_str):
        print(f"i={i+1},j={j}")
        print(f'\t lead_str[i]={lead_str[i]},T_str[j]={T_str[j-1]}')
        if lead_str[i] == T_str[j-1]:
            i += 1
            j += 1
        else:
            # 子串
            j = next_j[j - 1]
            # """
            # 如果T_str[j-1]==T_str[k-1],若不等，则nextval[j]=next[j];
            # 若相等，则nextval[j]=nextval[k]
            #
            # """
            # k=next_j[j - 1]
            # if T_str[j-1]!=T_str[k-1]:
            #     nextval[j-1]=next_j[j-1]
            # else:
            #     nextval[j-1]=nextval[k-1]
            # print(f"i={i},j={j},k={k},next_j={next_j[j-1]}")
            # j=nextval[j-1]
            if j == 0:
                i += 1
                j += 1
        print(f'nextval:{nextval}')
    return True if j -1== len(T_str) else False


if __name__ == "__main__":
    lead_s1 = "".join("a c a b a a b a a b c a c a a b c".split())#'abacaba'  # 'aaaaaaaaaabccccc'#'ababcabcacbab'
    T_s ="".join("a b a a b c a c".split()) #'aba'  # "aaab"#'abcac'

    lead_list=["".join("a c a b a a b a a b c a c a a b c".split()),'abacaba',
               'aaaaaaaaaabccccc','ababcabcacbab','cddcdc','aaabaaaab']
    sub_list=["".join("a b a a b c a c".split()),'abb',"aaab",'abcac','cda','aaaab']
    for i ,j in zip(lead_list,sub_list):
        # print(string_BF(lead_s1, T_s))
        print(i,len(i),j,len(j))
        print(string_KMP(i,j))
        print(''.center(100,'='))